package priv.conceit.study.leetcode.simple.official;

import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;

/**
 * 编号559
 * N叉树的最大深度
 * <a href="https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/"></a>
 * <p>
 * 给定一个 N 叉树，找到其最大深度。
 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
 * 例如，给定一个 3叉树 :
 * <a href="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/narytreeexample.png"/>
 * 返回它的最大深度 3
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/16
 */
public class MaximumDepthOfNAryTree {


	public static void main(String[] args) {

	}

	/**
	 * 队列实现
	 *
	 * @param root
	 * @return
	 */
	public int maxDepth(Node root) {
		int depth=0;
		int count=0;
		if(Objects.isNull(root)){
			return depth;
		}
		Queue<Node> nodeQueue=new LinkedList<>();
		nodeQueue.add(root);
		while (!nodeQueue.isEmpty()){
			//每次循环就是一层
			depth++;

			//队列当前的size需要单独提取出来
			int curNodeQueueSize=nodeQueue.size();

			//每一层进行遍历
			for (int i=0;i<curNodeQueueSize;i++){
				count++;

				Node curNode=nodeQueue.poll();
				if(Objects.nonNull(curNode.children)){
					for (int j=0;j<curNode.children.size();j++){
						nodeQueue.add(curNode.children.get(j));
					}
				}

			}

		}
		System.out.println("depth-->"+depth);
		System.out.println("count-->"+count);
		return depth;
	}

	class Node {
		public int val;
		public List<Node> children;

		public Node() {}

		public Node(int val,List<Node> children) {
			val = val;
			children = children;
		}
	};
}
